基本概念？
- 点连通度（图的连通度）：对应一个图 $G$，对于所有点集 $U \subset V_G$，也就是 $V_G$ 的子集中，使得 $G-U$（在图 $G$ 中删去 $U$ 和与 $U$ 关联的边）要么是一个非连通图，要么就是一个平凡图，其中最小的集合 $U$ 的大小 $|U|$ 就是图 $G$ 的点连通度（有时候也直接称为图的连通度）。
连通图&非连通图（无向图）
- 如果无向图 $G$ 中任意一对顶点都是连通的，此图是
连通图； - 相反，如果一个无向图不是连通图，则称为
非连通图。
强连通&单连通&弱连通（有向图）
- 如果对有向图 $G$ 中任意两个顶点 $u$ 和 $v$，既存在从 $u$ 到 $v$ 的路径，也存在从 $v$ 到 $u$ 的路径，则称该有向图 $G$ 为
强连通有向图； - 如果仅存在从 $u$ 到 $v$ 的路径，或从 $v$ 到 $u$ 的路径，则称该有向图 $G$ 为
单连通有向图； - 如果忽略有向图 $G$ 中每条有向边的方向，得到的无向图（即该有向图的基图）是连通图，则称该有向图 $G$ 为
弱连通有向图。
平凡图&非平凡图
- 只有一个节点，没有边的图为
平凡图； - 有至少两个节点，一条边的图，为
非平凡图。
- 如果无向图 $G$ 中任意一对顶点都是连通的，此图是
只许删点，求至少要删掉几个点，即一个图 $G$ 最少要去掉多少个点会变成非连通图或者平凡图：对于一个完全图 $K_n$ 来说，它的（点）连通度为 $n-1$。
完全图：若一个图的每一对不同顶点恰有一条边相连。
- 边连通度：同理，边连通度就是对于一个非平凡图 $G$，至少去掉多少条边才能使得该图变成非连通图。
只许删边，求至少要删掉几条边。
如何求解？
对于任意一个图，如何求该图的（点）连通度和边连通度呢？
有向图的边连通度其实就是一个最小割问题。- 求解思路
- 将原图 $G$ 中每条边$\lt u, v \gt$设置为容量为1的边，其它都不需要修改，即可得到对应的流网络图
- 任意选取一个节点 $u$ 作为源点，枚举其他所有与节点 $u$ 不相邻的节点作为汇点，求所有汇点情况下的各个最大流
- 其中最小的那个最大流即为原图的边连通度
- 最小的最大流中，所有流量为1的边组成的边集即为最小的边割集（割边集/割集）
设 $E’$ 是连通图 $G$ 的边集的子集，在 $G$ 中删去 $E’$ 后图不连通，则称 $E’$ 是 $G$ 的
割边集- 如果割边集 $E’$ 的任何真子集都不是割边集，则称 $E’$ 为
极小割边集 - 边的数目（图 $G$ 的边连通度）最小的极小割边集称为
最小割边集
如果割边集中只有一条边，则该边可以称为
割边（或桥） - 如果割边集 $E’$ 的任何真子集都不是割边集，则称 $E’$ 为
- 求解思路
有向图的点连通度- 求解思路
- 点连通度的流网络构造方法其实是将点连通度的求解转化为了边连通度的求解；
- 对于有向图 $G$，将每个节点 $u$ 拆分成 $u1$ 和 $u2$ 两个节点，并添加一条 $u1$ 到 $u2$ 容量为1的边$\lt u, v \gt$；
- 对于原图 $G$ 中的边$\lt u, v \gt$，对应在新网络中有边$\lt u2, v1 \gt$，容量为正无穷，即可得到对应的流网络图。
实际上：
原图 $G$ 上节点 $u$，$v$ 和从 $u$ 到 $v$ 的边<u,v>在对应的流网络中为节点 $u1$，$u2$，$v1$ 和 $v2$ 以及边<u1,u2>（容量为1）；<u2,v1>（容量为正无穷）；<v1,v2>（容量为1），也是一条路径。
- 也是在上述对应的流网络上任意选取一个节点 $u$ 作为源点，枚举所有其他不相邻的节点求最大流，其中最小的那个最大流即为原图 $G$ 的点连通度。
- 点连通度的流网络构造方法其实是将点连通度的求解转化为了边连通度的求解；
- 最小的最大流中，所有流量为1的边\lt u1, u2 \gt$对应的原图中的同一节点 $u$ 组成的点集即为最小的点割集（割顶集/割点集）
设 $V’$ 是连通图 $G$ 的一个顶点子集，在 $G$ 中删去 $V’$ 和与 $V’$ 关联的边后图不连通，则称 $V’$ 是 $G$ 的
割顶集- 如果割边顶集 $V’$ 的任何真子集都不是割顶集，则称 $V’$ 为
极小割顶集 - 顶点个数（图 $G$ 的（点）连通度）最小的极小割顶集称为
最小割顶集
如果割顶集中只有一个顶点，则该顶点可以称为
割点（或关节点） - 如果割边顶集 $V’$ 的任何真子集都不是割顶集，则称 $V’$ 为
- 求解思路
关于无向图：将图中的每条边 $(u, v)$ 拆成 $\lt u, v \gt$ 和 $\lt v, u \gt$ 两条边，即转成有向图处理。